//创建一个链表
public class MySingleLinkedList {
   static class ListNode{
        public int val;
        public ListNode next;//本身就是引用类型，在new对象的时候next就是空的

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//链表的头节点,把它定义在外面，利用其是成员变量，遍历局部变量的其他节点
    public void createList(){
        ListNode node1  =new ListNode(12);
        ListNode node2  =new ListNode(13);
        ListNode node3  =new ListNode(15);
        ListNode node4  =new ListNode(22);
        ListNode node5  =new ListNode(35);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        head=node1;//head指向node1


    }
    public  void display(){
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;

        }
        System.out.println();
    }
    public int size(){
        int count=0;
        ListNode cur=head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //头插法
    //以免数据出错，绑节点一般先绑后面
    public void addFirst(int val){
        ListNode node=new ListNode(val);
        node.next=head;
        head=node;
    }
    //后插法
    public void addLast(int val){
        ListNode node=new ListNode(val);
        if(head==null){
            head=node;
            return;
        }
        ListNode cur=head;
            while(cur.next!=null){//head不能为空，如果为空就空指针异常了
                cur=cur.next;


            }
        cur.next=node;

    }
    //任意位置插入
    public void addIndex(int index,int val){
        //判断index的合法性
        try{
            checkIndex(index);
        }catch (IndexNotLegalException e){
            e.printStackTrace();
        }
        if(index==0){
            addFirst(val);
            return;
        }
        if (index==size()){
            addLast(val);
            return;
        }
        //找到前一个节点
        ListNode cur=findIndexSubOne(index);
        ListNode node=new ListNode(val);
        node.next=cur.next;
        cur.next=node;


    }
    private ListNode findIndexSubOne(int index){
        int count=0;
        ListNode cur=head;
            while (count!=index-1){
                cur=cur.next;
                count++;
            }
            return cur;

            }
    private void checkIndex(int index)throws IndexNotLegalException{
        if(index<0||index>size()){
            throw new IndexNotLegalException("index不合法");
        }

    }
    public boolean contains(int val){
        ListNode cur=head;

        while (cur!=null){
            if(cur.val==val){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一个val值的节点
    public void remove(int val){
        if (head==null){
            return;
        }
        if(head.val==val){
            head=head.next;
            return;
        }
        //找到当前需要删除节点的前一个
        ListNode cur=head;
        while (cur.next!=null){
            if (cur.next.val==val){//这里把首节点漏掉了
                //找到了就开始删除
                ListNode del =cur.next;
                cur.next=del.next;
                return;
            }
            cur=cur.next;
        }
    }
    public void removeAllKey(int val){
    if(head==null){
        return;
    }
    ListNode prev=head;
    ListNode cur=head.next;
    //跳过我的头节点开始删除,prve是cur的前驱，cur是我要删除的对象
        while (cur!=null){
            if (cur.val==val){
                prev.next=cur.next;
                cur=cur.next;
            }else {

                cur=cur.next;
                prev=prev.next;
            }
        }
        //处理头节点
        if (head.val==val){
            head=head.next;
        }

    }
    public void clear(){
        head=null;
    }
    public ListNode reverseList(){
        if(head==null){
            return  head;

        }//cur curN head就是一个指向，可移动，并不代表固定哪一个数
        ListNode cur=head.next;
        head.next=null;
        while (cur!=null){
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
    }
    //指定位置开始打印
    public  void display(ListNode newHead){
        ListNode cur=newHead;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;

        }
        System.out.println();
    }
    //运用快慢指针取中间位置
    public  ListNode midNode(){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){//fast.next!=null不能放在前面，因为如果fast为空，fast.next报出空指针异常
            //fast=null是偶数的情况，fast.next=null是奇数的情况
            //只有在下两部都不为空的情况下，我们才能保证fast能跳两步
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //利用快慢指针，输出链表“倒数第k”的节点，fast先走k-1步，然后两个一起走，直到fast为空，返回slow
    public  int kthToLast(int k){
        if (k<=0||head==null){//head为空要返回，否则后面的会报空指针异常
            return -1;
        }
        ListNode fast=head;
        ListNode slow=head;
        int count=0;

        while (count!=k-1){
            fast=fast.next;
            if(fast==null){
                return -1;
            }

            count++;
        }

         while(fast.next!=null){

             fast=fast.next;
             slow=slow.next;
         }
         return slow.val;
    }
    //输入一个x，小于x的放在左边，大于x的放在右边，且不能改变原来的顺序
    //先设置两个链表，然后让两个链表连接，用尾插法，定义一个bs（beforestart），---be(beforeend)，as，as
    public ListNode partition(int x){
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        //cur开始遍历我的链表
        ListNode cur=head;
        while (cur!=null){
            if (cur.val<x){
                if (bs==null){
                    bs=be=cur;//遍历第一个数
                }else {//第二次及以后
                    be.next=cur;//先让be连接到cur，因为可能数的岔开be可能并不是连接cur
                    be=be.next;//前面的这个区间插入cur
                }

                cur=cur.next;
            }else {//大于x的情况
                if (as==null){
                    as=ae=cur;

                }else {
                    ae.next=cur;
                    ae=ae.next;
                }
                cur=cur.next;

            }
        }
        if(be==null){
            return bs;//如果be是空，就会产生空指针异常，
        }
        be.next=as;//进行拼接，但是如果be是空，就会产生空指针异常，
        if(as!=null){
            ae.next=null;//如果后半部分不为空，后半部分最末尾的next置空
        }
        return bs;
    }
    //对于一个链表，设计一个时间复杂度为o（n），空间复杂度为o1的算法来判断是否为回文串
    //空间复杂度o1，所以不能额外申请空间
    //做法：------先找到中间节点，翻转部分链表
        public boolean chkPalindrome(){
        if(head==null){
            return true;
        }
        //找到中间结点
            ListNode fast=head;
            ListNode slow=head;
            while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //return slow.val;(这里还没有走完不需要return）
            //翻转中间节点后面的链表
            ListNode cur=slow.next;//保证cur是slow的下一个，且cur是我当前要处理的节点
            while(cur!=null){
               ListNode curN=cur.next;
               cur.next=slow;
               slow=cur;
               cur=curN;
            }
            //slow从后往前，head从前往后，直到相遇
            while (head!=slow){
                if(head.val!=slow.val){
                    return  false;//数值相等才往下走
                }
                if(head.next==slow){//偶数的情况要考虑到
                    return  true;
                }
                head=head.next;
                slow=slow.next;



            }
            return true;
        }
        //给你一个头节点，判断链表是否有环
    public boolean hasCycle(){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return  true;
            }
        }
        return  false;
    }
        //给定一个链表的头节点，返回链表开始入环的第一个节点，如果没环则返回null
    //fast走一步，slow走两步，设head到入口点的距离为x，相遇点到入口点的距离为y，环的长度为c，可以得出x=(n-1)c+y，
        // 可以得出相遇点是固定的，可以得出head到入口点====入口点到相遇点（下半部分）
    public ListNode detectCycle(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){//情况一，因为条件不满足往下执行
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;//因为相遇跳出
            }
        }
        if(fast==null||fast.next==null){
            return  null;
        }
        //此时我们算出我们要的点,fast移到head，slow在交点，两个一起走，直到相遇
        fast=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return  fast;


    }
    //定义一个cur，让cur走到最后一个节点，然后让cur指向前面有个节点
    public void createLoop(){
        ListNode cur=head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=head.next;
    }




}
